Gulf War illness (GWI) is a complex multi-symptom illness which causes as much disability as other major medical diseases such as cancer and chronic heart failure. Previous clinical trials (i.e. cognitive behavioral therapy and graded exercise) for GWI have sought to improve disability by increasing activity regardless of symptom presentation. These previous trials for GWI have shown limited efficacy and poor adherence. An innovative treatment approach is to target a specific component of GWI, namely problem-solving ability, known to be associated with disability. Impairment in problem-solving ability affects over 70% of Gulf War Veterans (GWV) with GWI and is prospectively related to 1.5 times greater risk of disability. This impairment is also related to poorer adherence to medical regimes, making it difficult for GWV to manage other aspects of GWI. Thus, rehabilitation of problem-solving deficits is a critical target to treat a complicated syndrome like GWI. Despite this, there are no established treatments to compensate for problem-solving deficits among GWV. We are proposing to treat the problem-solving deficits of GWI using a state-of-the-art evidence-based approach to cognitive rehabilitation, Problem-Solving Therapy. Problem-Solving Therapy teaches patients skills to overcome factors impacting problem-solving. Because Problem-Solving Therapy teaches patients strategies to address real-life problems it leads to reductions in disability in other populations. This is the first trial of cognitive rehabilitation therapy for GWI. We propose a mult-site randomized controlled trial of telephone-delivered Problem-Solving Therapy versus telephone-delivered Health Education. We will use a 12 session established Problem-Solving Therapy intervention with a structured five step sequential approach to teaching problem-solving. Disability will be measured by the overall composite score from the World Health Organization Disability Assessment Schedule 2.0 which reflects two dimensions of disability: activity limitations and participation restrictions. In order to increase the representativeness of our sample, we will recruit 258 GWV from three VA sites: New Jersey, upstate New York, and Massachusetts.